Introduction

Public-key encryption is the miracle of modern cryptography. Prior to its invention, all secure communication used private-key cryptography and relied on the assumption that the two communicating parties shared a secret knowledge, i.e. a secret key. Public-key encryption completely revolutionised that because it made it possible to achieve secure communication without any secret knowledge which all participants need to have.

Public-Key Encryption

Public-key encryption uses two keys - a public encryption key and a private decryption key. When Alice wants to communicate with Bob, she generates a pair of public-private keys and sends Bob her public key, while keeping the private key for herself. This key can then be used by Bob to encrypt any message and only Alice, who has the private key, can decrypt it. Similarly, Bob can generate his own key pair and send Alice his public key. She would then be able to encrypt any message and Bob, who has his own private key, is the only one who can decrypt them.

Interestingly, anyone can send private messages to Alice or Bob, since they can just post their public keys on the Internet. This is the great advantage of public-key encryption - the public key cannot be used to decrypt messages, only to encrypt them. Nevertheless, the public and the private key are linked - to decrypt a message encrypted with a specific public key, you need to use its corresponding private key. This notion can be formalised as follows.

Definition: (Valid) Public-Key Encryption Scheme

A public-key encryption scheme consists of three algorithms:

$Gen$ is a probabilistic key-generation algorithm which outputs a pair of keys $(k_{e}, k_{d})$ with lengths $(n_{e}, n_{d})$ , respectively.
$Enc$ is an encryption algorithm which takes an encryption key $k_{e}$ and a message $m \in {0, 1}^{l}$ and outputs a ciphertext $c = Enc (k_{e}, m)$ .
$Dec$ is a decryption algorithm which takes a decryption mey $k_{d}$ and a ciphertext $c \in {0, 1}^{C}$ and outputs a plaintext $m = Dec (k_{d}, c)$ .

To be a valid public-key encryption scheme, the three algorithms must satisfy the following correctness property - for every message $m \in M$ and $(k_{e}, k_{d}) \leftarrow Gen ()$ :

$(k_{e}, k_{d}) \leftarrow Gen () Pr [Dec (k_{d}, Enc (k_{e}, m)) = m] > 1 - negl ()$

Definition Breakdown

The key-generation algorithm $Gen$ is a probabilistic algorithm which generates public-private key pairs that can be used for encryption and decryption. The encryption function $Enc$ takes a public key and encrypts messages with it, while the decryption algorithm $Dec$ takes a private key and decrypts ciphertexts.

The encryption scheme is considered valid, if for any public-private key pair $(k_{e}, k_{d})$ , generated by $Gen$ , and any message $m$ , decrypting the ciphertext $c : = Enc (k_{e}, m)$ with the key $k_{d}$ should result in the original plaintext $m$ with almost 100% certainty.

As with private-key encryption schemes, the message space is denoted by $M : = {0, 1}^{l}$ , and the ciphertext space is $C : = {0, 1}^{C}$ . However, there are two key spaces when using public-key encryption - $K_{e} : = {0, 1}^{n_{e}}$ denotes the public-key space, and $K_{d} : = {0, 1}^{n_{d}}$ denotes the private-key space.

It turns out that any reasonable definition of security for public-key encryption requires a probabilistic encryption function and key-generation algorithm and so decryption is allowed to fail with negligible probability - for example, when a prime number is needed but $Gen$ returns a composite.

The Cyberclopaedia

Introduction

Public-Key Encryption